package com.判断二叉搜索树的后序遍历;

public class Solution {
	public boolean VerifySquenceOfBST(int[] sequence) {
		int length = sequence.length;
		if(length<1)return false;
		return VerifyCore(sequence, 0, length - 1);

	}

	private boolean VerifyCore(int[] sequence, int start, int end) {
		//System.out.println("这次递归 start:"+start+" end:"+end);
		int length = end - start + 1;
		if (length < 2)
			return true;
		int index = 0;
		int root = sequence[end];
		for (int i = start; i <=end; i++) {
			if (sequence[i] >= root) {// 若是等于则代表比遍历到了最后一个,即此树只有左子树
				index = i;// 此时在index的左边的数都是应该小于root,从index包括index右边开始的数都大于root
				break;
			}
		}
		//System.out.println("这次递归 index:"+index);
		
		for (int j = index; j < end; j++) {
			if (sequence[j] < root)
				return false;
		}
		return VerifyCore(sequence, start, index - 1) && VerifyCore(sequence, index, end - 1);
	}
}
